package com.sicheng.lc.lc笔试.京东篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/27 20:13
 */
public class 漂亮串 {


    /**
     * 字符串里出现至少2个“red”子串就是漂亮串
     * 给一个数字n
     * 长n的漂亮串有多少种形式 答案很大 模 1e9+7
     * 1<=n<=1e6
     * <p>
     * 例如： redred，redavfred是漂亮串
     * xsdredrexs 不是
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(beauty(n));
    }


    static final int N = (int) 1e6 + 10;
    static final long mod = (int) (1e9 + 7);
    // 长n的字符串 不包含red的数量
    static final long[] dp0 = new long[N + 1];
    static final long[] f = new long[N + 1];

    // 预处理 dp的过程有难度 不好想
    static {
        f[0] = 1;
        //初始化 26^n
        for (int i = 1; i <= N; i++) {
            f[i] = f[i - 1] * 26 % mod;
        }
        dp0[0] = 1;
        dp0[1] = f[1];
        dp0[2] = f[2];
        dp0[3] = f[3] - 1;
        for (int i = 4; i <= N; i++) {
            // r _ _ _ _ _
            // r e d _ _ _
            // 第一位随便取 后面 i-i位不出现red
            // 但是一旦相邻的出现ed 也会出现red
            // 再扣除掉 高三位是red的情况 ===> 就是一共i位不出现red的情况
            dp0[i] = (f[1] * dp0[i - 1] - dp0[i - 3] + mod) % mod;
        }
    }

    // 长n的字符串 只存在一个red
    // 枚举每一处red出现的位置 red之前和之后的位置都没有red
    static long f1(int n) {
        long res = 0;
        for (int i = 0; i < n - 2; i++) {
            res = (res + dp0[i] * dp0[n - i - 3]) % mod;
        }
        return res;
    }


    // 方法1:
    // 用所有的情况 扣除掉没有red 和只存在1个red的情况
    // 分析复杂度  O(n~N)
    // 预处理只进行一次 占用第一个用例的时间，但是第一个用例数据肯定不大，后面每个用例可以全局共享dp，用到了java语言本身的技巧
    static long beauty(int n) {
        return (f[n] - dp0[n] - f1(n) + mod * 2) % mod;
    }

    // 方法2：
    // 长n且 至少存在2个red
    // 枚举2个red的位置 ，第一个red之前没得red，2个red直接也没得red，第二个red之后随便取
    // 复杂度 N2
    private static long f2(int n) {
        long res = 0;
        for (int i = 0; i < n; i++) {
            long v = dp0[i];
            for (int j = i + 3; j < n - 2; j++) {
                res = (res + getMod(v, dp0[j - i - 3], f[n - j - 3])) % mod;
            }
        }
        return res;
    }

    static long getMod(long... nums) {
        long res = 1;
        for (long x : nums) {
            res = res * x % mod;
        }
        return res;
    }
}
